package com.wangp.mywrite.coding;

/**
 * @author tooStrongerW
 * @version 1.0
 * @date 2021/4/2 21:12
 */
public class HeapSort extends Sort {

    public static void main(String[] args) {
        for (int i = 0; i < 1000; i++) {
            int[] arr = genRandomArr(10_000 );
            heapSort(arr);
            checkArrOrder(arr);
        }
    }

    private static void heapSort(int[] arr) {
        // 构建大顶堆
        buildHeap(arr);
        // 开始交换堆顶元素到堆的末尾并不断调整堆
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            adjustHeap(arr, 0, i - 1);
        }
    }

    private static void buildHeap(int[] arr) {
        for (int i = (arr.length / 2) - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length - 1);
        }
    }

    private static void adjustHeap(int[] arr, int parent, int len) {
        // 保存当前位置的值
        int tmp = arr[parent];
        // 左子节点
        int leftChildren = parent * 2 + 1;
        // 当左子节点存在
        while (leftChildren <= len) {
            // 右子节点
            int rightChildren = leftChildren + 1;
            // 当右子节点存在并大于左子节点时，开始扫描右子节点的数值
            if (rightChildren <= len && arr[rightChildren] > arr[leftChildren]) {
                leftChildren++;
            }
            // 如果左右子节点均不大于父节点的值，退出
            if (tmp > arr[leftChildren]) {
                break;
            }
            // 交换最大值
            swap(arr, leftChildren, parent);
            // 往子节点继续探寻
            parent = leftChildren;
            leftChildren = leftChildren * 2 + 1;
        }
    }
}
